package DataStructureAndAlgorithm.CSP.Day04;
import java.util.*;
//有顺序的广搜
public class AcWing_3208 {
    static class pair{
        int x;
        int y;
        pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] nums = new int[n + 1][n + 1];
        boolean[][] st = new boolean[n + 1][n + 1];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                nums[i][j] = in.nextInt();
            }
        }
        boolean isJi = false;
        Deque<pair> deque = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        deque.add(new pair(0,0));
        while (!deque.isEmpty()){
            int size = deque.size();
            Deque<pair> deque_temp = new LinkedList<>();
            for (int i = 0; i < size; i++){
                pair temp = deque.pollFirst();
                deque_temp.add(new pair(temp.x,temp.y));
                if (temp.y + 1 < n && !st[temp.x][temp.y + 1]){
                    deque.add(new pair(temp.x,temp.y + 1));
                    st[temp.x][temp.y + 1] = true;
                }
                if (temp.x + 1 < n && !st[temp.x + 1][temp.y]){
                    deque.add(new pair(temp.x + 1,temp.y));
                    st[temp.x + 1][temp.y] = true;
                }
            }
            int size_temp = deque_temp.size();
            for (int i = 0; i < size_temp; i++){
                pair temp_;
                if (isJi){
                    temp_ = deque_temp.pollFirst();
                    res.add(nums[temp_.x][temp_.y]);
                }else {
                    temp_ = deque_temp.pollLast();
                    res.add(nums[temp_.x][temp_.y]);
                }
            }
            isJi = !isJi;
        }
        for (int e : res){
            System.out.print(e + " ");
        }
    }
}
/*
在图像编码的算法中，需要将一个给定的方形矩阵进行 Z

字形扫描(Zigzag Scan)。

给定一个 n×n
的矩阵，Z

字形扫描的过程如下图所示：

zig.png

对于下面的 4×4

的矩阵，

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

对其进行 Z
字形扫描后得到长度为 16

的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个 Z
字形扫描的程序，给定一个 n×n 的矩阵，输出对这个矩阵进行 Z

字形扫描的结果。
输入格式

输入的第一行包含一个整数 n

，表示矩阵的大小。

输入的第二行到第 n+1
行每行包含 n

个正整数，由空格分隔，表示给定的矩阵。
输出格式

输出一行，包含 n×n
个整数，由空格分隔，表示输入的矩阵经过 Z

字形扫描后的结果。
数据范围

1≤n≤500
，
矩阵元素为不超过 1000

的正整数。
输入样例：

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

输出样例：

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

 */